#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Swallow:

    def __getattr__(self, name):
        return Swallow()

    def __call__(self, *args, **kwargs):
        print('--call-- swallow')
        return Swallow()

    def __bool__(self):
        return False


class Node:
    __slots__ = ['value', 'next']

    def __init__(self, value=None, next=None):
        self.value = value

        if next:
            self.next = next
        else:
            self.next = Swallow()

    def show(self):
        self.show_v()
        self.next.show()

    def show_v(self):
        print('v: %s' % self.value)

    def next_clear(self):
        self.next = Swallow()


    def reverse(self):
        pre = Swallow()
        cur = self

        while cur:
            cur.next, pre, cur = pre, cur, cur.next

        return pre

    def has_cycle(self):
        slow, fast = self, self

        slow_dis = 0
        while fast and fast.next:       # 如果fast为null, 则不会再执行and之后的fast.next
            slow_dis += 1
            slow = slow.next
            fast = fast.next.next       # 可能取None/Swallow

            if slow is fast:
                slow.show_v()
                print('slow_dis is [%s]' % slow_dis)
                return slow

        return None

    def cycle_begin(self):
        meet_node = self.has_cycle()
        if not meet_node:
            return None

        n1 = self
        n2 = meet_node
        dis = 0
        while n1 != n2:
            dis += 0
            n1, n2 = n1.next, n2.next

        return n1

    def kth(self, k):
        ''' 下标从1开始 '''
        if k <= 0:
            return None

        probe = self  # 这是第一个: k = 1

        k -= 1
        while k:
            k -= 1

            if probe:
                probe = probe.next
            else:
                return None

        return probe

    def half(self):
        pass

    def reverse_kth(self, k):
        ''' 倒数第kth 元素, 下表从1 开始
            [1, 2, 3, 4, 5] 倒数第1个是5
            [1, 2, 3, 4, 5] 倒数第2个是4
        '''

        k_node = self.kth(k)
        k_node.show_v()
        if not k_node:
            return k_node

        n1, n2 = self, k_node
        while n2.next:
            n1, n2 = n1.next, n2.next

        return n1


def build_link_list():
    l5 = Node(5, None)
    l4 = Node(4, l5)
    l3 = Node(3, l4)
    l2 = Node(2, l3)
    l1 = Node(1, l2)

    # l2 = Node(2, None)
    # l1 = Node(1, l2)

    # l1 = Node(1, None)

    return l1

def build_cycle_list():
    l7 = Node(7, None)
    l6 = Node(6, l7)
    l5 = Node(5, l6)
    l4 = Node(4, l5)
    l3 = Node(3, l4)
    l2 = Node(2, l3)
    l1 = Node(1, l2)

    # l5.next = l2
    l6.next = l3

    # l2 = Node(2, None)
    # l1 = Node(1, l2)

    # l1 = Node(1, None)

    return l1

def main():
    print("start main")
    l = build_link_list()

    print('=================== show =====================')
    l.show()

    h = l.reverse()
    print('=================== reverse =====================')
    h.show()

    print('=================== cycle =====================')
    l2 = build_cycle_list()
    print('l  has cycle [%s]' % bool( h.has_cycle()))
    print('l2 has cycle [%s]' % bool(l2.has_cycle()))

    print('=================== begin cycle =====================')
    node = l2.cycle_begin()
    node.show_v()

    print('=================== reverse kth  =====================')
    l = build_link_list()
    node = l.reverse_kth(1)
    print(node.value)

    node = l.reverse_kth(2)
    print(node.value)

    node = l.reverse_kth(5)
    print(node.value)

    node = l.reverse_kth(6)     # 超过1位
    print(node.value)


if __name__ == "__main__":
    main()
